#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 买卖股票的最佳时机含手续费：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
using namespace std;
class Solution {
public:
    //1.状态表示：
    //             f[i]:到i位置，其是买入状态的最大利润
    //             g[i]:到i位置，其是卖出状态的最大利润
    //2.状态转移方程：
    //             f[i]=max(f[i-1],g[i-1]-p[i])
    //             g[i]=max(g[i-1],f[i-1]+p[i]-fee)
    //3.初始化：f[0]=-p[0],g[0]=0
    //4.返回值： max(g[n-1],f[n-1])
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<int> f(n);
        auto g=f;
        f[0]=-prices[0],g[0]=0;
        for(int i=1;i<n;i++)
        {
            f[i]=max(g[i-1]-prices[i],f[i-1]);
            g[i]=max(g[i-1],f[i-1]+prices[i]-fee);
        }
        return max(f[n-1],g[n-1]);
    }
};